package main

func main() {

	//[1,2,2,null,3,null,3]

	root := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val:  2,
			Left: nil,
			Right: &TreeNode{
				Val:  3,
				Left: nil,
			},
		},
		Right: &TreeNode{
			Val:  2,
			Left: nil,
			Right: &TreeNode{
				Val:  3,
				Left: nil,
			},
		},
	}
	println(hasPathSum(root, 6))
}

// 我们做过一道题目：求数组的目标和，我们知道...利用的targetSum- nowValue。
// 深度搜索，我们把每一条路径都当做数组，求合
func hasPathSum(root *TreeNode, targetSum int) bool {

	// 怎么发现我都在用递归，难道递归能解决所有的树问题 ？
	var sumf func(node *TreeNode, needValue int) bool
	sumf = func(node *TreeNode, needValue int) bool {
		if node == nil {
			return false
		}

		// 如果到了树的叶子节点：
		if node.Left == nil && node.Right == nil {
			return node.Val == needValue
		}

		return sumf(node.Left, needValue-node.Val) || sumf(node.Right, needValue-node.Val)
	}

	return sumf(root, targetSum)
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
